We were talking about constraint satisfaction problems and yesterday we kind of went into

one of the techniques we have for constraint satisfaction, for finding solutions.

I would like to remind you, the constraint satisfaction problem, we kind of, from a general

case, we refined into constraint networks and constraint networks only have binary constraints.

That is sufficient because we can kind of stick the unary constraints into the domains

and we can encode higher constraints to binary constraints.

So all we're left with is binary constraints.

The theory of those is relatively simple, which is why we do it here.

In practice, you actually want to implement special methods for higher constraints, at

least because otherwise with this encoding trick that we're using, you lose quite a lot

of structure and even imagine giving error messages or something like this on an encoded

problem that the user has never seen.

So you want to do something practical, you implement the whole thing, but for the theory

and the ideas, it's sufficient to have binary constraints.

So what are we dealing with?

We have a set of n variables.

All of those have their own domain, which might be different, but all of which are finite

for the time being.

And the third component is the constraints, which are just relations between these domains

and we only have one, so we have constraints that are undirected.

So that's essentially what we're dealing with and all the ideas I'm showing you apply to

these, but can be transferred to higher arities as well.

We looked at Sudoku, we looked at the constraints, and why doesn't this work?

Okay, well, and they're relatively easy to write and we can see already that in this

case we have inequality constraints in certain situations.

We developed a set of names for the things we're dealing with.

We're dealing with partial assignments where we're going from the empty assignment, which

is a very, very, very partial assignment.

It assigns no variable to total assignments, which are our solutions.

And the process by which we do that is called extension, which just basically means you

assign more variables.

Quite simple.

With that we can interpret CSP as search, but not actually search on the state spaces.

That's something I would like you to wrap your mind around.

We're not doing search on the state spaces, but on partial assignments.

This is something we can only do because we have a factored state representation.

And one partial assignment covers lots of states.

So that's the idea here.

We basically convinced ourselves that we have an NP-complete problem, which just basically

means it's an interesting one.

Anything that's below NP-complete, in the worst case, it's just boring.

We cannot expect to be better.